Mobile devices, such as mobile telecommunication terminals (cellphones, smartphones, PDAs, and the like), must operate for long periods before being recharged. These mobile devices usually include multiple processors. Many power management techniques have been suggested to reduce the power consumption of processors in mobile devices.
One such technique, known as Dynamic Voltage and Frequency Scaling (DVFS), includes altering the voltage supplied to a processor as well as the frequency of the clock signal according to the computational load demands of the processor.
Processors equipped with DVFS will typically have a few operating points, where each operating point corresponds a supply voltage level and a corresponding operating frequency. Operating points allowing for higher operating frequencies require higher voltages, and cause higher energy consumption. Transitions between operating points may take a number of execution cycles, while the power level of the supply changes. It is often the case that while transition takes place, the processor must operate at the lower of the two frequencies involved in the transition.
Prior art approaches to DVFS have been limited. For example, it is known to use a mode control monitor to detect a level of activity of a processor, and switch discrete operating points. This approach does not consider real-time requirements, or have a clear algorithm to decide which operating point to execute under. It is also known to monitor task activities to switch power levels dynamically when the system reaches a maximum power threshold. In other approaches, task-level monitoring is used to define performance level intervals. It is also known to map tasks to processors to balance the load amongst processors, and then reduce supply voltage to some or all of the processors.
A paper by P. Grosse, at al, titled “Methods for Power Optimization in SOC-based Data Flow Systems,” published in May 2009 in ACM Transactions on Design Automation Electron. Syst. describes a method, based on linear programming, to assign at compile time an operating frequency to each of a number of hardware functional units, executing in a data-triggered, self-timed manner, so that the temporal requirements (throughput, latency) of a modem application are met, while minimizing power consumption. This, however, assumes that a single operating point is assigned per functional unit. Also, it assumes that concurrent applications are data flow graphs with no cyclic dependencies. It further assumes that between frames there is no pipelined behavior: the execution of an iteration of the data flow graph must be fully finished before the next iteration starts. Furthermore, it assumes that operating points are given by a continuous function, i.e., in any given interval, all frequencies are available. This problem cannot be solved optimally in polynomial time, and therefore the authors resort to a linearization of the objective function (minimize energy consumption) that allows them to model the problem as a linear program.
The April 2003 paper “Energy Aware Scheduling for Distributed Real-Time Systems” only considers systems where all processors must always switch frequency/power operating points at the same time. Furthermore, it cannot handle cyclic graphs, and it can only stretch the execution times to meet a deadline for an acyclic task graph. It divides the execution of all tasks in phases and assigns an operating point to each phase. This is not done optimally, but using a heuristic. It considers only static scheduling of task graphs. It also assumes that any operating point is possible in a continuous range.
Most of these prior art approaches assume a single operating point per task. Also, most assume continuous frequency levels, and most do not handle data flow graph cyclicity (i.e., cyclic dependencies between tasks in a task graph).